package leetcode.to1000;

import org.junit.Test;

public class T0678 {

    public boolean checkValidString(String s) {
        int minCount = 0, maxCount = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                minCount++;
                maxCount++;
            } else if (c == ')') {
                minCount = Math.max(minCount - 1, 0);
                maxCount--;
                if (maxCount < 0) {
                    return false;
                }
            } else {
                minCount = Math.max(minCount - 1, 0);
                maxCount++;
            }
        }
        return minCount == 0;
    }
    public boolean checkValidString2(String s) {
        //这个方法不对，不能判断出多的（
        char[] chars = s.toCharArray();
        int left = 0, right = 0, x = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') left++;
            if (chars[i] == ')') right++;
            if (chars[i] == '*') x++;
            if (right > left + x) return false;
        }
        if (Math.abs(left - right) <= x) {
            return true;
        } else {
            return false;
        }
    }
    @Test
    public void test() {
        String str = "(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())";
        checkValidString(str);
        checkValidString2(str);
    }

}
